/**
 * @program: data_structures_algorithms
 * @description: 希尔排序
 * @author: lld
 * @create: 2020/09/08 20:00
 **/
public class ShellSort {
    public static void main(String[] args){
        int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        //希尔排序
        int length = array.length;
        //增量每次减半
        for (int gap = length/2; gap>0;gap/=2 ) {

            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < length; j += gap) {//这个循环里其实就是一个插入排序
                    int temp = array[j];
                    int k = j;
                    if(array[k-gap]>temp){
                        while (k-gap >= 0 && temp < array[k - gap]) {
//                将前一个元素值赋值给当前元素
                            array[k] = array[k-gap];
                            k-=gap;
                        }
                    }
                    array[k] = temp;
                }
            }
        }
//        cur = arr[i];
//        j = i;
////            当前面那个元素更小，不需要插入
//        if (arr[j - 1] > cur) {
//            while (j > 0 && cur < arr[j - 1]) {
////                将前一个元素值赋值给当前元素
//                arr[j] = arr[j - 1];
//                j--;
//            }
//        }
//        arr[j] = cur;
        System.out.println();
        System.out.println("排序之后：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
}
